package com.example.algorithm.service.impl;

import com.example.algorithm.model.TreeNode;
import com.example.algorithm.service.GraphService;
import org.springframework.stereotype.Service;

import java.util.LinkedList;
import java.util.Queue;

/**图
 * @author Administrator
 * @date 2024/7/31 17:07
 * @description
 */
@Service
public class GraphServiceImpl implements GraphService {
    /**
     *NO.50  岛屿数量
     *
     * 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
     *
     * 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
     *
     * 此外，你可以假设该网格的四条边均被水包围。
     * @param grid
     * @return
     * 解法一：深度优先搜索
     * 解法二：广度优先搜索
     * 解法三：并查集
     *
     *
     */
    @Override
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0){
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int count=0;
        for(int row=0;row<m;row++){
            for(int col=0;col<n;col++){
                if(grid[row][col]=='1'){
                    count++;
                    judgeIsland(grid,row,col);
                }
            }
        }

        return count;
    }
    /**
     * 判断是否为孤岛
     * @param grid
     * @param row
     * @param col
     */
    private void judgeIsland(char [][] grid ,int row,int col){
        if(row>=grid.length||col>=grid[0].length){
            return;
        }
        if(row<0||col<0){
            return;
        }
        if(grid[row][col]=='0'){
            return;
        }
        grid[row][col]='0';
        judgeIsland(grid,row-1,col);
        judgeIsland(grid,row+1,col);
        judgeIsland(grid,row,col-1);
        judgeIsland(grid,row,col+1);

    }

    /**NO.51  腐烂的橘子
     * 在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
     *
     * 值 0 代表空单元格；
     * 值 1 代表新鲜橘子；
     * 值 2 代表腐烂的橘子。
     * 每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
     *
     * 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
     * @param grid
     * @return
     *
     * 解法一：多源广度优先搜索
     * 解法二：暴力循环
     */
    @Override
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<int[]>();
        int fresh=0;
        int minute=0;
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==2){
                    queue.offer(new int[]{i,j});
                }
                if(grid[i][j]==1){
                    fresh++;
                }
            }
        }
        while (fresh>0&&!queue.isEmpty()){
            minute++;
             int size= queue.size();
             for(int i=0;i<size;i++){
                 int []tmp = queue.poll();
                 int x=tmp[0] ,y=tmp[1];
                 if(x-1>=0&&grid[x-1][y]==1){
                     grid[x-1][y]=2;
                     queue.offer(new int[]{x-1,y});
                     fresh --;
                 }
                 if(x<grid.length-1&&grid[x+1][y]==1){
                     grid[x+1][y]=2;
                     queue.offer(new int[]{x+1,y});
                     fresh --;
                 }
                 if(y-1>=0&&grid[x][y-1]==1){
                     grid[x][y-1]=2;
                     queue.offer(new int[]{x,y-1});
                     fresh --;
                 }
                 if(y<grid[0].length-1&&grid[x][y+1]==1){
                     grid[x][y+1]=2;
                     queue.offer(new int[]{x,y+1});
                     fresh --;
                 }
             }

        }
        return fresh>0?-1:minute;
    }

    /**NO.52  课程表
     * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
     *
     * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
     *
     * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
     * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
     *
     * 解法
     *    拓扑排序解决
     *     １．将入度为０的节点加入队列
     *     ２．出队列的时候将这个顶点的所有临界点的入度减１，并将出队列的元素加入结果集合，如果入度为０则继续入队列
     *     ３．最后检查结果集合中的元素是否和课程数相同
     *
     * 解法一：深度优先算法
     * 解法二：广度优先搜索
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    @Override
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] inDegree = new int[numCourses];
        Queue<Integer> queue = new LinkedList<>();
        for(int[] pre:prerequisites){
            inDegree[pre[0]]++;
        }
        for(int i=0;i<numCourses;i++){
            if(inDegree[i]==0){
                queue.offer(i);
            }
        }
        while (numCourses>=0&&!queue.isEmpty()){
            int tmp = queue.poll();
            numCourses--;
            for(int[] pre:prerequisites){
                if(pre[1]==tmp){
                    inDegree[pre[0]]--;
                    if(inDegree[pre[0]]==0){
                        queue.offer(pre[0]);
                    }
                }
            }

        }
        return numCourses==0;
    }
}
